/*
 * @lc app=leetcode.cn id=70 lang=cpp
 *
 * [70] 爬楼梯
 */

// @lc code=start
class Solution {
private:
    int dict[1024];

public:
    int climbStairs(int n) {
        memset(dict, 0, sizeof(dict));
        dict[1] = 1;
        dict[2] = 2;
        return cal(n);
    }

    int cal(int n)
    {
        if(dict[n] != 0)
        {
            return dict[n];
        }
        dict[n - 1] = cal(n - 1);
        dict[n - 2] = cal(n - 2);
        return cal(n - 1) + cal(n - 2);
    }
};
// @lc code=end

